package algorithm.leetcode.medium;

/*
 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，
 其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

 */

import java.util.Arrays;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/21
 */
public class Question238 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        Question238 question = new Question238();
        int[] res = question.productExceptSelf(nums);
        System.out.println(Arrays.toString(res));
    }

    /**
     * 思路：  乘积 = 左边元素乘积 * 右边元素乘积
     */
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int k = 1;
        // 记录当前数的左边元素乘积
        for (int i = 0; i < res.length; i++) {
            res[i] = k;
            k *= nums[i];
        }
        k = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            res[i] *= k;
            k *= nums[i];
        }
        return res;
    }
}
